home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Solutions Folder / Problem 03 - Perimeter / Solution.p < prev   
Encoding:
Text File  |  1998-06-11  |  2.8 KB  |  119 lines  |  [TEXT/CWIE]
  1. (*
  2. Problem 12 - Perimeter
  3.  
  4. You are in charge of protecting a set of defenseless homeowners from predators that roam the area by constructing a fence of minimum length that encloses all of the homes.  
  5.  
  6. The prototype for your solution is as follows:
  7.  
  8. typedef struct Node {
  9.     UInt32 nodeNum,
  10.     SInt32 xCoord;
  11.     SInt32 yCoord;
  12. } Node;
  13.  
  14. void Perimeter(
  15.     UInt32 numHomes,
  16.     Node homesToEnclose[],
  17.     UInt32 *numNodesInPerimeter,
  18.     UInt32 nodesInPerimeter[]
  19. );
  20.  
  21. You are given a list homesToEnclose of numHomes homes to protect by constructing a fence around the homes. You should return a list nodesInPerimeter of the numNodesInPerimeter homes to be connected by a fence.  The fence must enclose all of the homes using the minimum amount of fencing material.
  22. *)
  23.  
  24. unit Solution;
  25.  
  26. interface
  27.  
  28. // Do not modify the interface
  29.  
  30.     uses
  31.         Types, Files;
  32.         
  33.     type Node = record
  34.             xCoord: SInt32;
  35.             yCoord: SInt32;
  36.         end;
  37.     type NodeArray = array [0..0] of Node;
  38.     type UInt32Array = array [0..0] of UInt32;
  39.         
  40.     procedure Perimeter( numHomes: UInt32; const homesToEnclose: NodeArray; var numNodesInPerimeter : UInt32; var nodesInPerimeter: UInt32Array);
  41.  
  42. implementation
  43.  
  44. // Fill in your solution and then submit this folder
  45.  
  46. // Team Name: Example Solution
  47. // 45 minutes
  48.  
  49.     function tabs( n: SInt32 ): SInt32;
  50.     begin
  51.         if n < 0 then begin
  52.             n := -n;
  53.         end;
  54.         tabs := n;
  55.     end;
  56.     
  57.     function theta( const n1, n2: Node ): real;
  58.         var
  59.             dx, dy: SInt32;
  60.             ax, ay: SInt32;
  61.             t: real;
  62.     begin
  63.         dx := n2.xCoord - n1.xCoord;
  64.         dy := n2.yCoord - n1.yCoord;
  65.         ax := tabs(dx);
  66.         ay := tabs(dy);
  67.         if (dx = 0) & (dy=0) then begin
  68.             t := 0;
  69.         end else begin
  70.             t := dy/(ax+ay);
  71.         end;
  72.         if dx < 0 then begin
  73.             t := 2-t;
  74.         end else if dy < 0 then begin
  75.             t := 4 + t;
  76.         end;
  77.         theta := 90 * t;
  78.     end;
  79.     
  80.     procedure Perimeter( numHomes: UInt32; const homesToEnclose: NodeArray; var numNodesInPerimeter : UInt32; var nodesInPerimeter: UInt32Array);
  81.         var
  82.             i: UInt32;
  83.             first, last, best: UInt32;
  84.             minangle, bestangle, thisangle: real;
  85.     begin
  86.         numNodesInPerimeter := 0;
  87.         if numHomes = 1 then begin
  88.             numNodesInPerimeter := 1;
  89.             nodesInPerimeter[0] := 0;
  90.         end else if numHomes >= 2 then begin
  91.             best := 0;
  92.             for i := 1 to numHomes-1 do begin
  93.                 if homesToEnclose[i].yCoord < homesToEnclose[best].yCoord then begin
  94.                     best := i;
  95.                 end;
  96.             end;
  97.             first := best;
  98.             minangle := 0;
  99.             last := best;
  100.             repeat
  101.                 nodesInPerimeter[numNodesInPerimeter] := last;
  102.                 Inc(numNodesInPerimeter);
  103.                 bestangle := 360;
  104.                 best := -1;
  105.                 for i := 0 to numHomes-1 do begin
  106.                     thisangle := theta( homesToEnclose[last], homesToEnclose[i] );
  107.                     if (i <> last) & (minangle <= thisangle) & (thisangle <= bestangle) then begin
  108.                         best := i;
  109.                         bestangle := thisangle;
  110.                     end;
  111.                 end;
  112.                 last := best;
  113.                 minangle := bestangle;
  114.             until (last = first) | (last = -1);
  115.         end;
  116.     end;
  117.     
  118. end.
  119.